{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f54c3e29-a357-492d-9f9e-7a6c88524fc4",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/lru-cache\n",
    "\n",
    "\n",
    "Runtime: 1048 ms, faster than 5.28% of Go online submissions for LRU Cache.\n",
    "Memory Usage: 72.6 MB, less than 52.07% of Go online submissions for LRU Cache.\n",
    "\n",
    "\n",
    "```go\n",
    "type LRUCache struct {\n",
    "\thistory  []int\n",
    "\tdict_    map[int]int\n",
    "\tcapacity int\n",
    "}\n",
    "\n",
    "func is_in_list(value int, list []int) bool {\n",
    "\tfor _, num := range list {\n",
    "\t\tif value == num {\n",
    "\t\t\treturn true\n",
    "\t\t}\n",
    "\t}\n",
    "\treturn false\n",
    "}\n",
    "\n",
    "func is_in_dict_keys(key int, dict map[int]int) bool {\n",
    "\t_, ok := dict[key]\n",
    "\treturn ok\n",
    "}\n",
    "\n",
    "func remove_value_from_list(value int, list []int) []int {\n",
    "\tfor i, num := range list {\n",
    "\t\tif num == value {\n",
    "\t\t\treturn append(list[:i], list[i+1:]...)\n",
    "\t\t}\n",
    "\t}\n",
    "\treturn list\n",
    "}\n",
    "\n",
    "func Constructor(capacity int) LRUCache {\n",
    "\t//4:08\n",
    "\treturn LRUCache{history: make([]int, 0), dict_: make(map[int]int), capacity: capacity}\n",
    "\t//4:26\n",
    "    //debug until 4:47\n",
    "}\n",
    "\n",
    "func (this *LRUCache) Get(key int) int {\n",
    "\tif is_in_dict_keys(key, this.dict_) {\n",
    "\t\tthis.history = remove_value_from_list(key, this.history)\n",
    "\t\tthis.history = append(this.history, key)\n",
    "\t\treturn this.dict_[key]\n",
    "\t} else {\n",
    "\t\treturn -1\n",
    "\t}\n",
    "}\n",
    "\n",
    "func (this *LRUCache) Put(key int, value int) {\n",
    "\tif is_in_dict_keys(key, this.dict_) {\n",
    "\t\tthis.history = remove_value_from_list(key, this.history)\n",
    "\t\tthis.history = append(this.history, key)\n",
    "\t\tthis.dict_[key] = value\n",
    "\t} else {\n",
    "\t\tif len(this.history) >= this.capacity {\n",
    "\t\t\told_key := this.history[0]\n",
    "\t\t\tthis.history = this.history[1:]\n",
    "\t\t\tthis.history = remove_value_from_list(old_key, this.history)\n",
    "\t\t\tdelete(this.dict_, old_key)\n",
    "\t\t}\n",
    "\t\tthis.dict_[key] = value\n",
    "\t\tthis.history = append(this.history, key)\n",
    "\t}\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b3413490-04b8-47c6-9713-90822b6e1ba3",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Go",
   "language": "go",
   "name": "gophernotes"
  },
  "language_info": {
   "codemirror_mode": "",
   "file_extension": ".go",
   "mimetype": "",
   "name": "go",
   "nbconvert_exporter": "",
   "pygments_lexer": "",
   "version": "go1.14.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}